package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import two.chapter_1.c1_1.Printer;

public class Ex1_4_22 {

    /**
     * 斐波那契数列  0 1 1 2 3 5 8 13 21 34 55 89 144
     * 得到斐波那契数列，最大值大于 数组长度的最小整数
     * 比如数组长度100， 那么斐波那契数列最大值为144
     * @param args
     */
    public static void main(String[] args) {
        int a[]={2,4,6,7,8,9,10,11};
        StdOut.println(rank(10,a));

    }

    private static int rank(int key,int []a ){
        int Fk=0;
        int Fk_1=0;
        int Fk_2=1;
        while (Fk < a.length)
        {
            Fk = Fk + Fk_1;
            Fk_1 = Fk_1 + Fk_2;
            Fk_2 = Fk - Fk_1;
        }

        int lo = 0;
        //Fn=Fn_1+Fn_2;
        while (Fk_2 >= 0)
        {
            int i = lo + Fk_2 > a.length - 1 ? a.length - 1 : lo + Fk_2;
            if (a[i] < key)
            {
                lo = lo + Fk_2;
            }
            else if (a[i] == key)
            {
                return i;
            }
            Fk = Fk_1;
            Fk_1 = Fk_2;
            Fk_2 = Fk - Fk_1;
        }

        return -1;
    }


}
